A key-agreement protocol is a means by which two parties initiate cryptographic tasks, such as, for example sending and receiving encrypted messages or authenticating a message which is received. The key-agreement protocol provides for an exchange of public keys, the result of this exchange is a common shared secret or session key. This shared secret or session key is used for the cryptographic tasks to be performed, for example to encrypt and decrypt further communications between the parties, in order to ensure that if messages are intercepted, the interceptor cannot decrypt these messages and gain access to the information they contain. The public key of the private-public key pair is widely distributed, but the private key is known only to its owner. Although the private and public keys are mathematically related, the parameters of the keys are chosen so that calculating the private key from the public key is either impossible or prohibitively expensive. For example, in elliptic curve cryptography, the private key is a number and the associated public key is a point on an elliptic curve obtained by scalar multiplication of a fixed basepoint on the elliptic curve by the private key. Calculating the private key from the associated public key requires the computation of an elliptic curve discrete logarithm, which is widely believed difficult for traditional computing platforms but is known to be simple for quantum computers. For another example, in lattice-based cryptography the private key is a vector in a high dimensional lattice and the associated public key is obtained by adding a small random perturbation to the private key. Calculating the private key from the associated public key requires solving the closest lattice vector problem, which is known to be difficult for traditional computing platforms and is widely believed to be difficult for quantum computers as well.
For ease of discussion and as is customary when describing electronic messaging between parties, we will identify the parties desiring to communicate as Alice and Bob. Alice and Bob each hold a private-public key pair. Alice's private key is designated as “a” and Alice's public key is designated as “A”, forming the private-public key pair (a, A). Likewise, Bob's private key is designated as “b” and Bob's public key is designated as “B”, forming the private-public key pair (b, B). In our discussions, Bob will be the sender of a communication and therefore will be referred to as the first party and Alice will be the intended recipient of the communication and will be referred to as the second party.
Pursuant to the key agreement protocol Alice, the second party, has made her public key A widely available by publishing it or otherwise transmitting it publicly to Bob, the first party. Bob computes the session key k using his private key b and Alice's public key A, and sends his public key, B, along with the message which was encrypted utilizing the session key k. When Alice receives Bob's public key, she utilizes Bob's public key (B) along with her private key (a) to calculate the session key. For example, the key agreement protocol may provide a session key protocol which defines the relationship between the first party's public key and the second party's private key and the session key, e.g. k=aB. Upon calculating the session key, Alice is able to decrypt the message. If on the other hand, the pubic key, B, received from Bob is incorrect, the session key calculated by Alice will not be correct and Alice will not be able to decrypt the message she received from Bob. Alice will likely report to Bob that she was unable to decrypt the message.
A valid key pair is one which is generated using the key agreement protocol. We will use the notation (b, B) to denote a valid key pair. In some instances, despite the fact that the key pair is valid, the valid key pair will not satisfy the session key protocol. The percentage of instances when a valid key pair does not satisfy the session key protocol is dependent upon the particulars of the key agreement used. An invalid key pair is one which was not generated using the key agreement protocol. We will use the notation (b′, B′) to denote an invalid key pair. In some instances, an invalid key pair (b′, B′) will satisfy the session key protocol. It is generally assumed that Bob will generate his private-public key pair (b, B) by following the key agreement protocol. The key agreement protocol is typically designed such that when properly followed, the number of valid private-public key pairs which will fail is very small relative to the number of valid private-public key pairs which will succeed in satisfying the session key protocol.
Alice's private key, a, is intended to remain private. If Bob wants to acquire Alice's private key, however, Bob can take advantage of the fact that some invalid keys will satisfy the session key protocol. In order to do so, Bob create an invalid key pair (b′, B′) and will send the invalid public key, B′ to Alice. When Alice receives the invalid public key B′, she will compute a session key, kA (kA=aB′). Bob's corresponding session key computation is kB=bA. Bob uses the session key to perform a cryptographic task, e.g. to encrypt a message. When Alice tries to decrypt the message received from Bob the cryptographic task of decryption will fail (e.g. Alice's attempt to decrypt will result in gibberish) because kA≠kB. By using an invalid key pair, Bob, Bob can increase the probability that the session key created by Alice will not allow Alice to perform the cryptographic task. With this information, Bob will know whether or not the invalid public key B′ he provided to Alice satisfied the equation aB′=b′A. Because Bob knows k (k=b′A) and Bob knows B′, Bob has learned some information as to the characteristics of Alice's private key (i.e., Bob knows whether a satisfies aB′=b′A). If the invalid key pair selected by Bob is randomly selected, it is highly likely that the session key generated by Alice will fail. If Bob always receives, notice that the session key failed, this information is not useful to Bob in determining a. If Bob can select an invalid key pair (b′, B′) which will succeed more frequently (ideally at a rate of 50%), however, the information he obtains from Alice will be much more useful in determining Alice's private key, a. If Bob can define a set of possible private keys, a, with a success/failure rate near 50%, each time Bob uses an invalid key pair (b′, B′), he eliminates 50% of the possible values of a. With repeated attempts to perform the cryptographic task, eventually, Bob would be able to determine Alice's private key. One way Alice may be able to avoid revealing such information about her private key to Bob is by first ensuring that Bob's public key is valid. For example, in elliptic curve cryptography, Bob's public key should represent a point on the elliptic curve, which Alice can easily test. This process is referred to as public key validation and is a standard security component of the key agreement processes. Although these types of checks may assist Alice for protocols intended to be secure against traditional computing platforms (e.g. elliptic curve), these types of checks will not suffice for protocols designed to be secure against a quantum computing system. Quantum-resistant key agreement protocols are based on technologies very different from those used in traditional public-key cryptography. For example, in lattice-based key agreements it is the case that public keys are indistinguishable from any other vector in space. Thus, these systems do not allow Alice to utilize any public key validation method to determine whether Bob followed the protocol when creating his public key, B.
Thus, there is a need for a new method of validating the public key to be used for transmitting and receiving encrypted messages which can be used with lattice-based and other quantum-resistant protocols.